package leetcode.code2070;

import java.util.Arrays;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution implements IDebug {

	public int[] maximumBeauty(int[][] items, int[] queries) {
		int len = queries.length;
		int[] ans = new int[len];
		Arrays.sort(items, (a, b) -> a[0] - b[0]);
		int lastPrice = items[0][0];
		int maxBeauty = items[0][1];
		int p = 1;
		for (int i = 1; i < items.length; i++) {
			int pricei = items[i][0];
			int beautyi = items[i][1];
			if (pricei == lastPrice) {
				if (beautyi > maxBeauty) {
					maxBeauty = beautyi;
					items[p - 1][1] = maxBeauty;
				}
			} else {
				maxBeauty = Math.max(maxBeauty, beautyi);
				items[p][0] = pricei;
				items[p][1] = maxBeauty;
				lastPrice = pricei;
				p++;
			}
		}
		for (int i = 0; i < queries.length; i++) {
			int queryPrice = queries[i];
			int l = 0;
			int r = p - 1;
			while (l <= r) {
				int mid = ((r - l) >> 1) + l;
				int[] item = items[mid];
				int itemPrice = item[0];
				int itemBeauty = item[1];
				if (itemPrice == queryPrice) {
					ans[i] = itemBeauty;
					break;
				} else if (itemPrice < queryPrice) {
					ans[i] = itemBeauty;
					l = mid + 1;
				} else {
					r = mid - 1;
				}
			}
		}
		return ans;
	}

	@Override
	public void debug1() {
		int[] e = HelpDebug.str2array3("[2,4,5,5,6,6]");
		HelpDebug.compare(e,
				this.maximumBeauty(HelpDebug.str2array1("[[1,2],[3,2],[2,4],[5,6],[3,5]]"), HelpDebug.str2array3("[1,2,3,4,5,6]")));

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();

	}

}
